import java.util.Hashtable;
import java.util.Random;

/*
用拉链法实现hash，接口：插入，查找，删除
hash函数，可以不实现
要求要手写链表实现
* */
public class HashTableTest {
    ListNode[] hash = new ListNode[10];

    public boolean insert(int key, int value){
        int hashcode = hashNum(key);
        ListNode node = hash[hashcode];
        if(node == null){
            hash[hashcode] = new ListNode(key, value);
        }else{
            ListNode tmp = node;
            while(tmp != null){
                if(hashNum(tmp.getKey()) == hashcode){
                    return false;
                }
                tmp = tmp.next;
            }
            tmp.next = new ListNode(key, value);
        }
        return true;
    }

    //查找
    public boolean search(int key){
        int hashcode = hashNum(key);
        ListNode node = hash[hashcode];
        if(node == null) return false;
        ListNode tmp = node;
        while(tmp != null){
            if(tmp.getKey() == key) return true;
            tmp = tmp.next;
        }
        return false;
    }

    //删除
    public ListNode remove(int key){
        int hashcode = hashNum(key);
        if(search(key) == false) return null;
        ListNode node = hash[hashcode];
        if(node == null) return null;
        ListNode tmp = node;
        ListNode prev = null;
        while(tmp != null){
            prev = tmp;
           if(tmp.getKey() == key) {
               prev.next = tmp.next;
               return tmp;
           }
        }
        return null;
    }


    public int hashNum(int key){
        return 3*4*7*23*245*key%hash.length;
    }

    static class ListNode{
        public ListNode(int key,int value){
            this.key = key;
            this.val = value;
        }
        int key;
        int val;
        ListNode next;
        int getKey(){
            return key;
        }
    }

    public static void main(String[] args) {

    }

}




